The present invention relates in general to systems and methods for representing polygons and determining the result of a resizing operation performed on a polygon, and more specifically to a system and method for accurately and efficiently computing a simple polygon (i.e., non-self-intersecting polygon) that results from a resizing operation performed on an original simple polygon.
Polygons are commonly utilized in a wide range of applications. For instance, polygons are often used in computer graphics. For example, computer-executable design applications often utilize polygons in defining a particular design (or layout). For instance, computer-executable applications for designing circuit layout, micro-mechanical device layout, and/or micro-electromechanical system (MEMS) layout, as examples, commonly use polygons in representing such layouts. Other example applications of polygons include uses in design and/or manufacturing in, for instance, generation of architectural designs of buildings, generation of representation of geographical terrain, generation of ornamental patterns for numerical control of sewing machines in the textile industry, numerical control of milling machines in the car body industry, mould design, design of solid fuel combustion chambers, the propagation of travelling shock waves, and obstacle avoidance problems of robotics. See e.g., Pham, B., xe2x80x9cOffset curves and surfaces: a brief survey,xe2x80x9d Computer Aided Design 24, pp. 223-229, 1992.
Many applications utilize xe2x80x9csimple polygons,xe2x80x9d which as used herein refers to polygons that are non-self-intersecting (but which may include holes therein). That is, a simple polygon is a polygon that does not intersect with itself (i.e., does not include edges that intersect each other). It should be noted that self-intersecting polygons can be decomposed into simple polygons. Thus, applications that include self-intersecting polygons may use simple polygons for representing the self-intersecting polygons and/or for manipulating the polygons (e.g., resizing the polygons).
Once a polygon is defined, it is often desired to resize it. That is, it is often desired to have the edges of the polygon moved outward (by a particular offset amount) to enlarge the polygon or moved inward (by a particular inset amount) to decrease the size of the polygon. Offsetting a polygon involves moving its boundary outward a particular distance (e.g., which is typically some user-specified distance in most applications) in a direction normal to the polygon""s boundary. Insetting moves the edges into the polygon. Resizing of a polygon (i.e., offsetting or insetting of the polygon) is a primitive operation that is required in a variety of applications, such as the example applications identified above. Resizing (e.g., offsetting or insetting) a polygon is sometimes referred to as polygon growth or polygon envelope.
As is well known in the art, various problems may be encountered when resizing a simple polygon. For instance, when resizing a polygon, any of several different types of events (which may be referred to herein as xe2x80x9cresizing eventsxe2x80x9d or as xe2x80x9ccritical eventsxe2x80x9d) may be encountered. More specifically, the geometry of a polygon may change significantly when an offset or inset operation is performed. One event that may be encountered is referred to herein as a xe2x80x9cself-intersectionxe2x80x9d event in which a simple polygon intersects with itself as a result of a resizing operation. Another event that may be encountered is referred to herein as an xe2x80x9cedge-collapsexe2x80x9d event in which an edge of the polygon effectively disappears as a result of a resizing operation. That is, the two vertices of an edge may become one as a result of a resizing operation, thereby causing such edge to effectively disappear. Another event that may be encountered is referred to herein a xe2x80x9cpolygon-splitxe2x80x9d event in which the polygon is effectively split into two (or more) separate polygons as a result of a resizing operation. Accordingly, it becomes desirable to have an algorithm for resizing polygons that robustly and efficiently handles such events that may be encountered during a resizing operation to accurately determine the polygon that results from such resizing operation.
The above events have been recognized in the prior art as events that need to be accounted for when performing resizing operations on a polygon. Various techniques for handling such events have been proposed in the prior art. As one example, a common approach for addressing the problems associated with offsetting a simple polygon is described by Tiller, W. and Hanson, H.G., xe2x80x9cOffsets of two-dimensional profiles,xe2x80x9d IEEE Computer Graphics and Applications 5, pp. 36-46, 1984. In this approach, a local offset of each edge of the polygon is performed first (i.e., every edge is moved a user-specified distance), and then an attempt is made to eliminate self-intersections and loops produced in the resulting polygon. That is, the local offsetting may lead to self-intersections and/or loops in the resulting offset polygon, and the ones of such self-intersections and/or loops that are xe2x80x9cnot neededxe2x80x9d are discarded. The process of identifying the loops that are xe2x80x9cnot neededxe2x80x9d is heuristic and is not guaranteed to work for all inputs. Accordingly, this procedure is heuristic in nature and does not provide a robust solution for resizing polygons.
More robust algorithms for performing resizing operations on a polygon have been proposed in the prior art that utilize the xe2x80x9cstraight skeletonxe2x80x9d (which may also be referred to as the xe2x80x9clineal axisxe2x80x9d) of the polygon in performing the resizing operation in order to handle one or more of the above-identified types of resizing events that may be encountered. That is, robust polygon resizing techniques of the prior art require first computing the straight skeleton of the polygon being resized. In general, the straight skeleton of a simple polygon is defined by shrinking the polygon by translating each of its edges at a fixed rate, keeping sharp corners at the reflex vertices, and monitoring where the vertices go. The straight skeleton is quite similar to the medial axis. In fact, the two are equivalent for convex polygons. However, the straight skeleton of a non-convex polygon has fewer edges than the medial axis, and all of its edges are line segments (the medial axis also has parabolic arcs around each reflex vertex). Computing the straight skeleton of a polygon is further described by Petr Felkel and Stepan Obdrzalek in xe2x80x9cStraight Skeleton Implementation,xe2x80x9d Proceedings of Spring Conference on Computer Graphics, Budmerice, Slovakia, ISBN 80-223-0837-4, pp. 210-218, 1998, and by Letlibe Phahlamohlaka in xe2x80x9cOffset Problems for Polygons,xe2x80x9d Masters thesis, Dept. of Mathematics, Statistics and Computer Science, Dalhousie University, Canada, 1991.
Once the straight skeleton data structure of a polygon has been computed, one can easily compute the insetted polygon. That is, the straight skeleton, by definition, detects all events when the polygon is inset. I am unaware of any teaching in the prior art of extending the straight skeleton algorithm to detect events that occur during an offset operation. Also, the straight skeleton provides a solution for edge-collapse and polygon-split events, but further computation is still required to generate a correct result when a self-intersection event is encountered.
As described further below, the robust resizing techniques of the prior art that require computation of the straight skeleton of a polygon are computationally expensive. In the case of convex polygons, resizing events can be determined by determining the medial axis of the polygon being resized. See Letlibe Phahlamohlaka, xe2x80x9cOffset Problems for Polygons,xe2x80x9d Masters thesis, Dept. of Mathematics, Statistics and Computer Science, Dalhousie University, Canada, 1991. The medial axis of a polygon can be constructed in linear time (see e.g., Francis Chin, Jack Snoeyink, and Cao An Wang, xe2x80x9cFinding the Medial Axis of a Simple Polygon in Linear Time,xe2x80x9d Proc. 6th Ann. Int. Symp. Algorithms and Computation (ISAAC xe2x80x295), Lecture Notes in Computer Science 1004, pp. 382-391, 1995). For non-convex polygons, however, the medial axis is not suitable for determining resizing events, and therefore robust algorithms of the prior art utilize the straight skeleton of such non-convex polygons to detect resizing events.
Although the medial axis of a polygon can be constructed in linear time, the fastest known algorithms for computing straight skeletons are much slower. The following table (Table 1) lists the time and space bounds of various algorithms proposed in the prior art for computing straight skeletons wherein n is the total number of vertices of the polygon, r is the number of reflex (non-convex) vertices of the polygon, and e is an arbitrarily small positive constant:
The references proposing an algorithm having the corresponding time and space requirements shown in Table 1 are identified therein as follows: A) Oswin Aichholzer, Franz Aurenhammer, David Alberts, and Bemd Gartner, xe2x80x9cA Novel Type of Skeleton for Polygonsxe2x80x9d, Journal of Universal Computer Science, 1 (12), pp. 752-761, 1995; B) Oswin Aichholzer and Franz Aurenhammer, xe2x80x9cStraight Skeletons for General Polygonal Figures in the Plane,xe2x80x9d Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON xe2x80x296), pp. 117-126, Lecture Notes in Computer Science 1090, Springer-Verlag, 1996; C) David Eppstein, xe2x80x9cFast hierarchical clustering and other applications of dynamic closest pairs,xe2x80x9d manuscript, July 1997; D) David Eppstein and Jeff Erickson, xe2x80x9cRaising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions,xe2x80x9d manuscript, July 1998 (an extended abstract of this paper was presented at Proc. 14th Annu. A CM. Symp. Computational Geometry, pp. 58-67, 1998); E) Robert Lang, xe2x80x9cA Computational Algorithm for Origami Design,xe2x80x9d Proc. 12th Ann. ACM Symp. Computational Geometry, pp. 98-105, 1996; F) Petr Felkel and Stepan Obdrzalek, xe2x80x9cStraight Skeleton Implementation,xe2x80x9d Proceedings of Spring Conference on Computer Graphics, Budmerice, Slovakia, ISBN 80-223-0837-4, pp. 210-218, 1998; and G) Siu-Wing Cheng and Antoine Vigneron, xe2x80x9cMotorcycle Graphs and Straight Skeletons,xe2x80x9d Proc. 13th Annu. ACM-SIAM Symposium on Discrete Algorithms, pp. 156-165, 2002.
Robust solutions for resizing polygons that have been proposed in the prior art generally utilize a straight skeleton, which results in the solutions being computationally expensive, as described in conjunction with Table 1 above. For instance, such algorithms proposed in the prior art have a running time greater than 0(n log n) (i.e., xe2x80x9con the order ofxe2x80x9d n log n). For example, Aichholzer et al. propose an algorithm for computing straight skeletons in xe2x80x9cStraight Skeletons for General Polygonal Figures in the Planexe2x80x9d that requires O(n2 log n) time in the worst case. In xe2x80x9cA Novel Type of Skeleton for Polygons,xe2x80x9d Aichholzer et al. propose an algorithm for computing straight skeletons that has a running time of O(nr log n), which may, in the worst case, be O(n2 log n) since r can be O(n). Aichholzer et al. recognized that such algorithm can be further improved to O(nr+n log n)=0(n2) using a quadtree-like data structure of size 0(nr). See also, Felkel P. and Obdrzalek, S., xe2x80x9cStraight Skeleton Computation,xe2x80x9d Lazlo Szirmay-Kalos, editor, Spring Conference on Computer Graphics, Budmerice, Slovakia, pp. 210-218, (April) 1998.
Eppstein et al. proposed the most computationally efficient algorithm of which I am aware for computing the straight skeleton of a polygon, which runs in O(n17/11+e (where xe2x80x9cexe2x80x9d is an arbitrarily small positive constant) and such algorithm is relatively complicated to implement. See xe2x80x9cRaising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions,xe2x80x9d manuscript, July 1998 (extended abstract presented at Proc. 14th Annu. ACM. Symp. Computational Geometery, pp. 58-67, 1998). Accordingly, the computational requirement with the best known technique increases at a rate of n17/11+e as the number xe2x80x9cnxe2x80x9d of vertices of a polygon increases.
Siu-Wing et al. propose an algorithm to calculate the straight skeleton of a polygon within running time of O(n1.5 log n), but it is not robust because it fails for some special cases, as described in xe2x80x9cMotorcycle Graphs and Straight Skeletons,xe2x80x9d Proc. 13th Annu. ACM-SIAM Symposium on Discrete Algorithms, pp. 156-165, 2002. For those special cases, Siu-Wing et al. revert to the algorithm proposed by Eppstein et al. Thus, the best known general, robust algorithm for calculating a straight skeleton is that proposed by Eppstein et al., which runs in O(n17/11+e), although the algorithm proposed by Siu-Wing et al. has a slightly better run time of O(n1.5 log n) for most cases. Also, Siu-Wing et al. is the only reference of which I am aware that addresses using a straight skeleton algorithm for polygons with holes.
Additionally, Kalmanovich et al. have proposed an algorithm to offset an arbitrary polygon which has an expected (but not guaranteed) performance of O(n log n). Kalmanovich G. and Nisnevich G., xe2x80x9cSwift and stable polygon growth and broken line offset,xe2x80x9d Computer-aided Design, Vol. 30(11) (1998) pp. 847-852. The approach proposed by Kalmanovich et al. does not compute a polygon""s straight skeleton. However, the algorithm proposed by Kalmanovich et al. is heuristic in nature and is not robust because it may output some spurious edges (which the authors refer to as xe2x80x9cdead-zone edgesxe2x80x9d).
In view of the above, robust techniques proposed in the prior art for resizing polygons generally utilize a straight skeleton, which results in the techniques being undesirably computationally expensive. For example, the most computationally efficient prior art technique for robustly computing a straight skeleton of a polygon is O(n17/11+e). Other techniques have been proposed in the prior art that are more computationally efficient, such as the heuristic approach described by Tiller et al. in xe2x80x9cOffsets of two-dimensional profilesxe2x80x9d and the heuristic approach described by Kalmanovich et al. in xe2x80x9cSwift and stable polygon growth and broken line offset,xe2x80x9d but such computationally efficient techniques are less robust in that they do not produce an accurate result for all inputs (i.e., they produce incorrect results in certain cases). Accordingly, a desire exists for a system and method for robustly determining a resulting resized polygon in a computationally efficient (inexpensive) manner.
The present invention is directed to a system and method which enable robust and efficient resizing of a simple polygon. That is, according to embodiments of the present invention, a system and method are provided that enable simple resizing operations to be performed robustly (i.e., capable of generating an accurate result for all inputs) on simple polygons in a computationally inexpensive manner. A preferred embodiment provides a solution that is relatively easy to implement. A preferred embodiment is operable to handle various resizing events that may be encountered when resizing a simple polygon, such as self-intersection, edge-collapse, and edge-split events, in order to accurately generate the correct resized polygon. Further, a preferred embodiment is operable to compute a resulting resized polygon with efficiency of O(n log n), even if one or more of the above types of events is encountered during the resizing process. Embodiments of the present invention handle resizing events for simple polygons (both convex and non-convex) without requiring construction of the straight skeleton of the polygons being resized. Also, embodiments of the present invention are operable for resizing simple polygons that may include holes.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims. The novel features which are believed to be characteristic of the invention, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that each of the figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present invention.